package com.dhu.graph.weightGraph;

import com.dhu.graph.basic.edge.Edge;
import com.dhu.graph.basic.GraphImpls.EdgeWeightGraph;
import com.dhu.graph.utils.unionFind.UnionFind;
import com.dhu.graph.utils.ArrayQueue;
import com.dhu.graph.utils.MinPQ;

/**
 * @ Author ：snow
 * @ Date   ：Created in 2020-05-10
 * @ Description：
 * 把所有的边都加入到优先队列中，然后不断地删除出权重最小的边，利用quick-u检查这条边是否已经失效，
 * 如果失效则跳过，没失效则将他加入到保存最小生成树的队列里，该算法一开始生成的是森林，直到pq队列中的边到达V-1
 * 这时森林连接成一颗最小生成树
 * @ Modified By：
 * @ Version:
 */
public class KruskalMST {
    private ArrayQueue<Edge> mst;

    public KruskalMST(EdgeWeightGraph G){
        // 将所有的边加入到优先队列中
        MinPQ<Edge> pq = new MinPQ<>();
        for (Edge e : G.edges()) {
            pq.insert(e);
        }
        UnionFind UF = new UnionFind(G.V());

        // 循环体中会增加一条边故为 < G.V() -1
        while (!pq.isEmpty() && mst.size() < G.V() - 1){
            Edge e = pq.deleteMin();
            int v = e.either(), w = e.other(v);
            if (UF.isConnected(v, w)) continue; // 失效边，跳过
            UF.quick_union(v,w);
            mst.enqueue(e);

        }
    }
    public Iterable<Edge> MSTEdges(){
        return this.mst;
    }
}
